<!DOCTYPE html>
<html lang="zh-cn">
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">




<title>线性排序 | Miles`s</title>

<link rel="stylesheet" href="https://mada.gitee.io/notes//css/styles.css">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.2.0/css/all.css" 
integrity="sha384-hWVjflwFxL6sNzntih27bfxkr27PmbbK/iSvJ+a4+0owXq79v+lsFkW54bOGbiDQ" crossorigin="anonymous">
<script src="https://code.jquery.com/jquery-3.3.1.js" integrity="sha256-2Kok7MbOyxpgUVvAk/HJ2jigOSYS2auK4Pfzbm7uH60=" crossorigin="anonymous"></script>


<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/zenburn.min.css" crossorigin="anonymous" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js" integrity="sha256-/BfiIkHlHoVihZdc6TFuj7MmJ0TWcWsMXkeDFwhi0zw=" crossorigin="anonymous"></script>
<script>hljs.initHighlightingOnLoad();</script>
<script src="https://mada.gitee.io/notes//js/highlight.js"></script>






<div class="container">
    <nav class="navbar level">
      <div class="navbar-brand">
          <a class="nav-item" href="https://mada.gitee.io/notes/"><h1 class="title is-3">Miles`s</h1></a>
      </div>           
      <div class="navbar-menu has-text-centered is-active">
          <div class="navbar-end is-centered">
              
           </div>
      </div>
    </nav>
  </div>
<div class="container">
  <h2 class="subtitle is-6">November 27, 2018</h2>
  <h1 class="subtitle is-size-4-mobile is-size-3-desktop">线性排序</h1>
  <div class="content">
    

<p>这类排序算法的时间复杂度是线性的，统称 <code>线性排序</code>。</p>

<p>之所以能够做到线性复杂度，原因就是：这些算法是非基于比较的排序算法，都不涉及元素之间的比较操作。</p>

<h3 id="桶排序-bucket-sort">桶排序(Bucket Sort)</h3>

<p><code>桶排序</code> 的核心思想是将要排序的数据分到若干个有序的“桶”中，每个桶里的数据再做单独排序。桶排完序之后，再把每个桶的数据按照顺序依次取出，组成的序列就是有序的了。</p>

<p>桶排序的时间复杂度为什么为：O(n)。</p>

<pre><code>数据：n 条
桶：m 个
每个桶数据：n/m 条
每个桶快排时间复杂度：O(k*logk)
m 个桶时间复杂度:O(m*k*logk) = O(m*(n/m)logk) = O(nlogk) = O(nlogn/m)
m ~= n 的时候，O(nlogn/m) ~= O(n)
</code></pre>

<p>也就是当桶个数与数据非常接近，log(n/m)是一个非常小的常量，这个时候的排序时间复杂度为 O(n)。</p>

<p>桶排序对数据要求非常苛刻：</p>

<ul>
<li>要排序的数据要很容易划分成 m 个桶。</li>
<li>桶与桶之间要有着天然的大小排序。这样内部数据排序之后，桶不需要再次排序。</li>
<li>每个桶的数据划分比较均匀，这样桶内部的时间复杂度就会接近一个很小的常数。</li>
</ul>

<p><code>桶排序适合用在外部排序中</code>。指数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。</p>

<h3 id="记数排序">记数排序</h3>

<p>可以理解为是 <code>桶排序</code> 的一种。
要排序的数据在一定的范围内，比如最大值为 k。我们把数据划分为 k 个桶，每个桶的数据值是相同的，这样省掉了排序的时间。</p>

<p>举个例子：有8个考生，分数在0～5之间，考生成绩分别为：2，5，3，0，2，3，0，3</p>

<pre><code class="language-java">
// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n &lt;= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i &lt; n; ++i) {
    if (max &lt; a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
  for (int i = 0; i &lt;= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入 c 中
  for (int i = 0; i &lt; n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i &lt;= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组 r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i &gt;= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i &lt; n; ++i) {
    a[i] = r[i];
  }
}

</code></pre>

<p><code>记数排序</code> 要求数据范围不大，而且最好是给非负数整数排序，如果数据含有负数，需要做一次运算，将所有的值加上一个常数以此将数据转化为正数。</p>

<h3 id="基数排序-radix-sort">基数排序（Radix Sort）</h3>

<p>以手机号码为例：将数据分为11位，从最后一位开始排序，然后最后第二位，以此类推，最后以第一位进行排序，最终得到有序列表。每一位的排序可以使用线性排序算法进行排序。
时间复杂度为 O(11*n) = O(n)</p>

<p>基数排序需要满足一些条件：</p>

<ul>
<li>数据可以分割出独立的位来排序，位之间有递进的关系。</li>
<li>每一位的数据范围不能太大，可以用线性排序算法排序。</li>
</ul>

<p>Notes：数据位数不同时，可以使用“0”补齐</p>

  </div>
</div>
<div class="container has-text-centered">
    
</div>

<div class="container has-text-centered">
  
</div>
<section class="section">
  <div class="container has-text-centered">
    <p></p>
  </div>
</section>


